package 第一章基础算法.快速排序.id786第K个数;

import java.util.Scanner;

/**
 * 输入格式
 * 第一行包含两个整数 n 和 k。
 * 第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整数数列。
 *
 * 输出格式
 * 输出一个整数，表示数列的第 k 小数。
 *
 * 数据范围
 * 1≤n≤100000,
 * 1≤k≤n
 */
class Main {
    public static void main(String[] args){
        //处理输入
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int nums[] = new int[n];
        for(int i = 0;i<n;i++){
            nums[i] = scanner.nextInt();
        }
        //快速选择
        int res = quickSelectSort(nums,0,n-1,k);
        //打印结果
        System.out.println(nums[res]);
    }

    public static int  quickSelectSort(int[] nums ,int l ,int r,int k){
        if(l >= r)return l;
        int p1 = l-1;
        int p2 = r+1;
        int pivot = nums[l];

        while (p1 < p2){
            do{p1++;}while (nums[p1] < pivot);
            do{p2--;}while (nums[p2] > pivot);
            if(p1 < p2){
                swap(nums,p1,p2);
            }
        }
        //关键处理，判断pivot左边元素的个数（x）
        int x = p2-l+1;
        int res = -1;
        //注意如果x = k-1，说明pivot位置就是第k小的数，此时继续递归左边
        if(x >= k){
            //递归左边
            res = quickSelectSort(nums,l,p2,k);
        }else {
            //递归右边
            res = quickSelectSort(nums,p2+1,r,k-x);
        }
        return res;
    }

    public static void swap(int[]nums, int a ,int b){
        int x = nums[a];
        nums[a] = nums[b];
        nums[b] = x;
    }
}
